
// 封装一个列表
function ArrayList() { 
    this.array = [];
    // 插入数据
    ArrayList.prototype.insert = function (item) { 
        this.array.push(item);
    }
    // 以字符串小形式输出数据
    ArrayList.prototype.toString = function () { 
        return this.array.join('-');
     }
    // 换位方法
    ArrayList.prototype.swap = function (m, n) { 
        let temp = this.array[m];
        this.array[m] = this.array[n];
        this.array[n] = temp;
     }
    // 排序算法
    // 1.冒泡排序
    // 总结：
    // 冒泡排序的比较次数是n(n-1)/2;
    // 冒泡排序的交换次数（真实的操作次数）是n(n-1)/2;（因为两次比较平均有一次交换，或者说一次比较有两种情况）
    // 但是不管哪种次数多大O表示法（时间复杂度）都是：n的平方
    ArrayList.prototype.bubbleSort = function () { 
        let length = this.array.length;
        for(var j = length -1; j>=0;j--) {
            // 第一次时候，i =0 ;i+1 = 1
            // 最后一次时候，i = length-1;i+1 = length,但是length取不到，所以要让最后一次i+1=length-1
            for(var i =0; i<j;i++) {
                if(this.array[i]>this.array[i+1]) {
                    this.swap(i, i+1);
                }
            }
        }
    }算法

    // 2.选择排序
    // 总结：
    // 选择排序的比较次数是n(n-1)/2;
    // 选择排序的交换次数（真实的操作次数）是n-1;
    // 比较操作的大O表示法（时间复杂度）都是：n的平方，交换操作的大O表示法（时间复杂度）都是：n
    ArrayList.prototype.selectionSort = function () { 
        let length = this.array.length;
        for(var j =0;j<length-1;j++) {
            let min = j;
            for(var i = min+1;i<length;i++) {
                if (this.array[min] > this.array[i]) {
                    min = i;
                }
            }
            this.swap(min, j);
        }
    }
    
    // 3.插入排序
    // 总结：
    // 插入排序的最多的比较次数是n(n-1)/2，平均的比较次数是n(n-1)/4
    // 插入排序的最多复制次数（真实的操作次数）是n(n-1)/2，平均复杂次数n(n-1)/4;
    // 效率高于冒泡排序和选择排序
    ArrayList.prototype.insertSort = function () {
        let length = this.array.length;
        for(var i =1 ; i<length;i++) {
            let temp = this.array[i];
            let j =i;
            while(j-1>=0 && this.array[j-1]>temp) {
                this.array[j] = this.array[j-1];
                j--;
            }
            this.array[j] = temp;
        }
    }

    // 4.希尔排序
    ArrayList.prototype.shellSort = function() {
        let length = this.array.length;
        // 1.获取初始增量
        let gap = Math.floor(length / 2);
        // 2.第一层循环是增量的变化
        while(gap >1) {
            // 3.第二层循环是遍历当前增量的每一组
            for(let i = gap;i<length;i++){
                let temp = this.array[i];
                //3.第三层循环是对每一组进行插入排序
                while(this.array[i-gap]>temp && i > gap-1) {
                    this.array[i] = this.array[i-gap];
                    i -= gap;
                }
                this.array[i] = temp;
            };
            gap = Math.floor(gap/2);
        }
    }

    // 5.快速排序
    // 5.1 获取枢纽de方法
    // 数据的第一项和最后一项的中位数项，然后将最大项放到最后一位，中位数项和length-2项对调
    ArrayList.prototype.median = function(left, right) {
        center = Math.floor((left + right) / 2);
        if (this.array[left] > this.array[center]) {
            this.swap(left, center);
        };
        if (this.array[left] > this.array[right]) {
            this.swap(left, right);
        };
        if (this.array[center] > this.array[right]) {
            this.swap(center, right);
        };

        if(this.array[right] >= this.array[center] && 
            this.array[center] >= this.array[left] ) {
            // console.log('枢纽排序成功');
            this.swap(center, right-1);
            return this.array[right - 1]; 
        }
        // console.log('枢纽排序失败');
    };

     // 快速排序
    ArrayList.prototype.quickSort = function () {
        let length = this.array.length;
        this.quick(0, length-1);
    };

    ArrayList.prototype.quick = function (left, right) { 
        // d递归结束的条件
        if(left >= right) return;
        // 获取枢纽
        let pivot = this.median(left, right);
        // 设置指针
        let i = left;
        let j = right - 1;
         while( i < j) {
             while(this.array[++i]  < pivot){};
             while(this.array[--j] > pivot){};
             if(j > i) {
                 this.swap(i, j)
             }
             else if(j <= i) {
                 break
             }
         };
         this.swap(i, right -1);
         //分而治之
         this.quick(left, i-1);
         this.quick(i+1, right);
     }



    //  6.归并排序
    ArrayList.prototype.mergeSort = function (left, right) {
        left = typeof left == 'number' ? left: 0;
        right = typeof right == 'number' ? right : this.array.length-1;
        let center = Math.floor((left + right) / 2);
        let i = left, j = center +1, k = 0;
        // 递归各自组
        // 递归结束条件
        if (left >= right) return;
        this.mergeSort(i, center);
        this.mergeSort(j, right);

        // 对比两组数组
        let temp = [];
        while(i < center && j < right) {
            if(this.array[i] < this.array[j]){
                temp[k++] = this.array[i++]
            }else {
                temp[k++] = this.array[j++]
            }
        }
        //处理剩余那项
        while(i < center) temp[k++] = this.array[i++]
        while(j < right) temp[k++] = this.array[j++]

        // 将最终结果赋回去
        temp.forEach((item,i)=>{
            this.array[left + i] = item;
        })
    }
 }




 /** 测试 */
 let list = new ArrayList();
 list.insert(88);
 list.insert(99);
 list.insert(21);
 list.insert(5);
 list.insert(76);
 console.log('数据的初始顺序：', list.toString());
 list.bubbleSort();
 console.log('冒泡排序：', list.toString());
 list.selectionSort();
 console.log('选择排序：', list.toString());
 list.insertSort();
 console.log('插入排序：', list.toString());
 list.shellSort();
 console.log('希尔排序：', list.toString());
 list.quickSort();
 console.log('快速排序：', list.toString());
 list.mergeSort();
 console.log('归并排序：', list.toString());